The present invention relates generally to the field of error correcting codes for data transmission and more particularly to a packet loss recovery technique for use in data packet-based networks providing real-time multimedia communications.
One of the most significant issues that must be dealt with in data packet-based communications networks such as, for example, the Internet, is the problem of error correction due to packet loss. Since each data packet is transmitted through the network independently (and potentially via entirely different network routes), it is common for a destination location to fail to receive an occasional sequence of one or more data packets, and to receive some such packets after an atypically substantial delay. And when such a network is employed to provide real-time multimedia communications such as, for example, voice communications, receiving some data packets after a substantial delay may be tantamount to not receiving them at all, since the receiver cannot typically wait to proceed with the processing of subsequent data packets.
A number of techniques, invariably involving some sort of redundancy coding, have been employed to address the general problem of error correction including the packet loss problem. Typically, the packet loss channel is recognized as an erasure channel using a channel coding language. Classical error correcting codes such as binary block codes, convolutional codes, and Reed Solomon codes, each familiar to those of ordinary skill in the art, can then be employed in an erasure correcting mode. (See, e.g., E. Ayanoglu et al., xe2x80x9cDiversity Coding for Transparent Self-Healing and Fault-Tolerant Communication Networks,xe2x80x9d IEEE Transactions on Communications, vol. 41, no. 11, pp. 1677-1685, November, 1993; and R. Urbanke et al., xe2x80x9cMethods and Apparatus for Packetizing Data for Transmission Through an Erasure Broadcast Channel,xe2x80x9d co-pending U.S. patent application, Ser. No. 08/892,855, filed Jul. 15, 1997 and assigned to the assignee of the present invention. U.S. patent application, Ser. No. 08/892,855, now U.S. Pat. No. 6,175,944, is hereby incorporated by reference as is fully set forth herein.) However, it is in fact considerably simpler to correct an erasure than to correct other types of errors (such as, for example, xe2x80x9crandomxe2x80x9d modifications of one or more symbols). In the case of an error, the location of the error must first be determined, while in the case of an erasure (e.g., an unreceived data packet), the location is known.
Typically, a random error correcting code can correct about twice as many erasures as errors in a given block. However, in the context of a transmission of a sequence of data packets across a network, a packet loss effectively causes a continuous string (a xe2x80x9cburstxe2x80x9d) of erased symbols. Since most classical channel codes are designed for the correction of random errors (or random erasures), prior art approaches to dealing with the packet loss problem typically perform some form of interleaving (permuting) on a relatively long sequence of packets. In this manner, a packet loss channel with correlated erasures (i.e., a continuous string of erased symbols) is transformed into an apparently random erasure channel. Unfortunately, performing such an interleaving process necessarily results in a significant delay at the destination, since the decoder must de-interleave the received data in order to recreate the original sequence of data packets.
Therefore, the use of channel codes such as, for example, Reed Solomon codes, when effectively applied across many packets in sequence, will necessarily require that relatively long delays be incurred at the receiver. As pointed out above, however, such delays may be prohibitive for real-time applications such as, for example, voice communication over networks based on the Internet protocol (IP). Recently, however, in U.S. Pat. No. 5,870,412 (xe2x80x9cForward Error Correction System for Packet Based Real Time Mediaxe2x80x9d) issued to G. M. Schuster et al. on Feb. 9, 1999 (hereinaiter, xe2x80x9cSchuster et al.xe2x80x9d), a method for data recovery in a bursty packet network which incurs a relatively short delay (as compared to other prior art techniques) has been presented.
Specifically, Shuster et al. performs forward error correction by appending checksum information to each data packet, wherein the checksum information is defined by taking a bit-by-bit exclusive-or sum of the information portion (the xe2x80x9cpayloadxe2x80x9d) from a preceding specified number of data packets. (Bit padding on the shorter payloads is used if the information payloads from the preceding packets are of unequal length.) By way of illustration, FIG. 1 shows an organization of an encoded data packet in accordance with the prior art packet loss recovery techniques as employed in Shuster et al. The illustrated data packet comprises coded information followed by checksum information which has been appended to the data packet for purposes of forward error correction. As described above, in the case of the Shuster et al. technique, the checksum information specifically comprises an exclusive-or sum of the information payload from a preceding specified plural number of data packets.
Thus, using the Shuster et al. technique, a single bit erasure correction code of length w+1 packet instances is formed, enabling for the correction of a burst of up to w lost data packets (provided such a burst is followed by a string of w correctly received data packets), with a maximum decoding delay of 2wxe2x88x921 packets. Clearly, the Shuster et al. method incurs an overhead in bit volume of at least 100% (more if bit padding is required), as compared to the bits of the information payloads alone. In addition, it can be seen that the method of Shuster et al. requires the solution of w exclusive-or equations.
In co-pending U.S. patent application Ser. No. 09/425,143, xe2x80x9cPacket Loss Control Method For Real-Time Multimedia Communicationsxe2x80x9d by H-L. Lou and C-E. W. Sundberg, filed on Oct. 21, 1999 and commonly assigned to the assignee of the present invention (hereinafter, xe2x80x9cLou et al.xe2x80x9d), a significantly improved technique over that of Shuster et al. was provided. U.S. patent application Ser. No. 09/425,143 is hereby incorporated by reference as if fully set forth herein. By way of illustration, FIG. 2 shows an organization of an encoded data packet in accordance with the prior art packet loss recovery techniques as employed in Lou et al.
In particular, while Shuster et al. generates checksum information by xe2x80x9ccombiningxe2x80x9d (e.g., by performing exclusive-or operations on) the payload information from a plurality of preceding data packets, Lou et al. simply xe2x80x9crepeatsxe2x80x9d information content from a particular one of the previous data packets in a later packet. More specifically, according to the technique of Lou et al , the information payload associated with a given data packet k, for example, might be identically copied and appended to data packet k+w. (That is, the information payload would be repeated with a delay of w transmitted packets.) Such an improved approach advantageously can correct for a burst of up to w lost data packets (as does the method of Shuster et al.) while improving the decoding delay to w packets as compared to the 2wxe2x88x921 decoding delay required by the method of Shuster et al. In fact, it can be shown that the decoding delay required by the technique of Lou et al., relative to the number of consecutive lost packets that can be properly corrected, is in fact optimal. (Note that each of these prior art approaches append forward error correcting data to the existing packets without adding any additional packets.)
Both of the above-described prior art approaches (i.e., those of both Shuster et al. and the improved method of Lou et al.), however, are limited to providing rate 1/2 convolutional forward error correcting codes (FEC). (As is fully familiar to those of ordinary skill in the art, the xe2x80x9cratexe2x80x9d of an error correcting code is determined based on the ratio between the total number of bits used to encode a given set of data being encoded, and the number of xe2x80x9cinformationxe2x80x9d bits which are being encoded therefrom.) Often, however, it is desirable to employ error correcting codes with rates which are greater than 1/2 for purposes of increased transmission efficiency. Therefore, it would be highly desirable to devise forward error correcting channel coding techniques having rates greater than 1/2, which, like the rate 1/2 technique of Lou et al., advantageously provide relatively high levels of channel protection against burst erasures with a relatively (if not optimally) low decoding delay, while still maintaining the existing number of transmitted packets and the existing packet structure.
In accordance with the principles of the present invention, a novel class of forward error correcting codes having coding rates greater than 1/2 are provided which provide high levels of channel protection against burst erasures with a relatively low decoding delay. In particular, a novel method of channel coding, in accordance with certain illustrative embodiments of the present invention comprises similarly dividing the source information (i.e., the data) contained in each packet to be coded into a plurality of (similar) corresponding portions, and then computing xe2x80x9cchecksumsxe2x80x9d over multiple data packets, each such checksum being based on different (i.e., non-corresponding) portions of at least two of the multiple packets. These xe2x80x9cchecksumsxe2x80x9d are then advantageously appended to various subsequent data packets to be coded (as in the above-described prior art techniques). However, by using different portions of multiple packets from which the checksums are computed, forward error correcting codes having rates greater than 1/2 which nonetheless provide relatively high levels of channel protection against burst erasures with relatively low decoding delays are advantageously provided. In accordance with illustrative decoder embodiments of the present invention, erased data packets may be regenerated based on the decoding of one or more subsequent (correctly received) data packets which include such appended xe2x80x9cchecksumxe2x80x9d data.
More specifically, in accordance with the present invention, a method of coding a sequence of data packets representing a continuous stream of information is provided, wherein each data packet comprises a set of payload information representative of a segment of said stream of information corresponding thereto, each set of payload information having been similarly divided into a plurality of corresponding individual payload information portions, the method or apparatus comprising steps or means for coding a plurality of said data packets, said coding of each of said data packets comprising coding said set of payload information comprised therein by coding at least one of said plurality of individual payload information portions thereof; and coding an additional one of said data packets, said additional data packet being subsequent in said sequence to each of said plurality of data packets, said plurality of data packets thereby being previous to said additional data packet, said coding of said additional data packet comprising coding said set of payload information comprised therein, said coded additional data packet further comprising an added set of payload information which provides forward error correcting capability for said payload information comprised in said plurality of previous data packets, wherein said added set of payload information comprised in said coded additional data packet is based on a combination of said payload information comprised in two or more of said previous data packets, and wherein said payload information comprised in at least two of said previous data packets upon which said added set of payload information is based comprises payload information from different individual payload information portions thereof.
In addition, in accordance with the present invention, a method and apparatus for decoding a coded sequence of data packets in response to an erasure of one or more of said data packets in said sequence is provided, wherein said sequence of data packets has been coded with use of the above described coding technique, and wherein the method or apparatus comprises steps or means for decoding said coded additional one of said data packets, said additional one of said data packets being subsequent in said sequence to at least one of said erased data packets, to generate at least one of said individual payload information portions thereof representative of said forward error correcting data; and reproducing said at least one of said erased data packets based on at least said generated individual payload information portion of said decoded additional one of said data packets.